Multi-level optimization of the canonical polyadic tensor decomposition at large-scale: Application to the stratification of social networks deflation

Tensors are multi-dimensional mathematical objects that allow to model complex relationships and to perform decompositions for analytical purpose. They are used in a wide range of data mining applications. In social network analysis, tensor decompositions give interesting insights by taking into consideration multiple characteristics of data. However, the power-law distribution of such data forces the decomposition to reveal only the strong signals that hide information of interest having a lighter in-tensity. To reveal hidden information, we propose a method to stratify the signal, by gathering clusters of similar intensity in each stratum. It is an iterative process, in which the CANDECOMP/PARAFAC (CP) decomposition is applied and its result is used to deflate the tensor, i.e., by removing from the tensor the clusters found with the decomposition. As the CP decomposition is computationally demanding, it is also necessary to optimize its algorithm, to apply it on large-scale data with a reasonable execution time, even with the several executions needed by the iterative process of the stratification. Therefore, we propose an algorithm that uses both dense and sparse data structures and that leverages coarse and fine grained optimizations in addition to incremental computations in order to achieve large scale CP tensor decomposition. Our implementation outperforms the baseline of large-scale CP decomposition libraries by several orders of magnitude. We validate our stratification method and our optimized algorithm on a Twitter dataset about COVID vaccines.(c) 2022 Elsevier Ltd. All rights reserved.

ERIS: An Approach Based on Community Boundaries to Assess Polarization in Online Social Networks

Detection and characterization of polarization are of major interest in Social Network Analysis, especially to identify conflictual topics that animate the interactions between users. As gatekeepers of their community, users in the boundaries significantly contribute to its polarization. We propose ERIS, a formal graph approach relying on community boundaries and users’ interactions to compute two metrics: the community antagonism and the porosity of boundaries. These values assess the degree of opposition between communities and their aversion to external exposure, allowing an understanding of the overall polarization through the behaviors of the different communities. We also present an implementation based on matrix computations, freely available online. Our experiments show a significant improvement in terms of efficiency in comparison to existing solutions. Finally, we apply our proposal on real data harvested from Twitter with a case study about the vaccines and the COVID-19. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.